package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;
/*
问题描述:如果一个字符串包含两个相邻的重复子串，则称它为容易的串，其他串称为困难的串,
如:BB，ABCDACABCAB,ABCDABCD都是容易的，A,AB,ABA,D,DC,ABDAB,CBABCBA都是困难的。

输入正整数n,L，输出由前L个字符(大写英文字母)组成的，字典序第n小的困难的串。
例如，当L=3时，前7个困难的串分别为:
A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA
n指定为4的话,输出ABAC
 */
public class hDFS_困难的串by剪枝 {
	static int count = 0;
	public static void main(String[] args) {
		hDFS_困难的串by剪枝 test = new hDFS_困难的串by剪枝();
		test.DFS_HardString("", 3, 7);
	}
	
	public void DFS_HardString(String prefix, int L, int n) {
		for (char i = 'A'; i < 'A' + L; i++) {
			if (isHard(prefix, i)) {//剪枝
				System.out.println(prefix + i);
				count++;
				if (count == n) {
					System.exit(0);
				}
				DFS_HardString(prefix + i, L, n);
				//没有回溯是因为，在一个节点A，A的1孩子被剪枝，2孩子的尝试不受影响
				//因为改变状态是通过剪枝才发生，没通过就没改变状态
			}
		}
	}
	
	public boolean isHard(String prefix, char newWord) {
		int width = 0;//每次s1.equals(s2)所比较的宽度；代码数值初始为0；但逻辑数值初始=1，意思说(width+1) = 逻辑上的宽度
		for (int j = prefix.length() - 1; j >= 0; j -= 2) {//开始(逻辑)宽度从1开始的比较；-2是为了配合宽度的增加；这里不懂去画图推到，或者死记硬背
			/*
					 0123
			string = abcd
			string.substring(3, 4) = d
			string.substring(3) = d
			string.substring(4) = ""(空串)
			
			string.substring(j, j + 4)
				表示从j索引开始，(算上j索引处的元素)往后数4个元素
				string.substring(0, 0+4) = abcd
				不会把第j + 4索引处的元素算进去
			所以s2的起始位置，就可以“偷懒地”设定成j + 4；这很巧妙地还保持了s1.length() == s2.length()
			
			看不明白就死记硬背，去看蓝桥杯7.17	10：16
			 */
			final String s1 = prefix.substring(j, j + (width + 1));//从后往前，截取被对比的串；截取的串的元素个数是width+1
			final String s2 = prefix.substring(j + (width + 1)) + newWord;//从后往前，截取并合并，要对比的串
			if (s1.equals(s2)) {
				return false;
			}
			width++;//宽度+1；+1为了判断其他宽度下是否存在串相同的情况
		}
		return true;
	}
}
